package LeetCode.month01.day14;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class No207 {
    static boolean flag;
    public static void main(String[] args) {
        int[][] pre = new int[][]{{0,1},{3,1},{1,3},{3,2}};
        System.out.println(canFinish(4, pre));
    }
    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> list = new ArrayList<>();
        int[] visited = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            list.add(new ArrayList<>());
        }
        flag = true;
        for (int i = 0; i < prerequisites.length; i++) {
            list.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        for (int i = 0; i < numCourses&&flag; i++) {
            if(visited[i]==0)
            dfs(list,visited,i);
        }
        return flag;
    }

    public static void dfs(List<List<Integer>> list,int[] visited,int row){
        visited[row]=1;
        for (int i = 0; i < list.get(row).size(); i++) {
            if(visited[list.get(row).get(i)]==0){
                dfs(list,visited,list.get(row).get(i));
                if(!flag) return;
            }else if(visited[list.get(row).get(i)]==1){
                flag = false;
                return;
            }
        }
        visited[row] = 2;
    }
}
